package com.zlp.partice;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

import static com.google.common.math.LongMath.gcd;

/**
 * @author: zhulaiping
 * @time: 2022/7/1 14:51
 */
public class Day20220701 {

    /*
    * 1.先求出列数
    *       先求高度
    * 2.层序遍历构建列表即可
    * */
    int height = 0;
    public List<List<String>> printTree(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i=0;i<size;i++){
                TreeNode poll = queue.poll();
                if(poll.left!=null) queue.offer(poll.left);
                if(poll.right!=null) queue.offer(poll.right);
            }
            height++;
        }
        queue.add(root);
        List<List<String>> ret = new ArrayList<>(height);
        int len = (int) Math.pow(2,height)-1;
        for (int i=0;i<height;i++){
            List<String> cur = new ArrayList<>(len);
            for (int j=0;j<len;j++){
                cur.add("");
            }
            ret.add(cur);
        }
        ret.get(0).set((len-1)/2,root.val+"");
        dfs2(ret,0,(len-1)/2,root);

        return ret;
    }

    private void dfs2(List<List<String>> ret, int i, int c, TreeNode root) {
        int val = (int) Math.pow(2,height-2-i);
        if(root.left!=null){
            int curJ = c-val;
            ret.get(i+1).set(curJ,root.left.val+"");
            dfs2(ret,i+1,curJ,root.left);
        }
        if(root.right!=null){
            int curJ = c+val;
            ret.get(i+1).set(curJ,root.right.val+"");
            dfs2(ret,i+1,curJ,root.right);
        }
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return dfs(nums,0,nums.length);
    }

    private TreeNode dfs(int[] nums, int start, int end) {
        if(start == end) return null;
        int index = 0,max = 0;
        for (int i=start;i<end;i++){
            if(max<nums[i]){
                index = i;
                max = nums[i];
            }
        }
        TreeNode node = new TreeNode(max);
        node.left = dfs(nums,start,index);
        node.right = dfs(nums,index+1,end);
        return node;
    }

    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int min = Integer.MAX_VALUE;
        List<List<Integer>> ret = null;
        for (int i=1;i<arr.length;i++){
            if(arr[i]-arr[i-1]>min) continue;
            if(arr[i]-arr[i-1]<min){
                min = arr[i]-arr[i-1];
                ret = new ArrayList<>();
            }
            ret.add(Arrays.asList(arr[i-1],arr[i]));
        }
        return ret;
    }
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] s = sentence.split(" ");
        Map<Character,TreeSet<String>> map = new HashMap<>();
        for (String str:dictionary){
            TreeSet<String> set = map.getOrDefault(str.charAt(0), new TreeSet<>());
            set.add(str);
            map.put(str.charAt(0), set);
        }
        for (int i=0;i<s.length;i++){
            if(map.get(s[i].charAt(0))==null) continue;
            for (String cur:map.get(s[i].charAt(0))){
                if(!compare(s[i],cur)) continue;
                s[i] = cur;
                break;
            }
        }
        return Arrays.stream(s).collect(Collectors.joining(" "));
    }


    /**
     * 1.如果大于0，直接进站
     * 2，如果小于0:
     *      2.1 粘为空或栈顶为负直接进
     *      2.2 比较舍弃当前或栈顶
     *          当前大，出栈
     *          相当，出栈
     *          当前小直接舍弃
     * @param asteroids
     * @return
     */
    public int[] asteroidCollision(int[] asteroids) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (int val:asteroids){
            if(val>0||stack.isEmpty()||stack.peek()<0) {
                stack.push(val);
                continue;
            }
            while (!stack.isEmpty()&&stack.peek()>0){
                if(val+stack.peek()<0) stack.pop();
                else break;
            }
            if(stack.isEmpty()||stack.peek()<0) stack.push(val);
            else if(stack.peek() + val == 0){
                stack.pop();
            }
        }
        int[] ret = new int[stack.size()];
        for (int i=0;i<ret.length;i++){
            ret[i] = stack.pollLast();
        }
        return ret;
    }
    public int oddCells(int m, int n, int[][] indices) {
        int[] row = new int[m];
        int[] column = new int[n];
        for (int[] indice:indices){
            row[indice[0]]++;
            column[indice[1]]++;
        }
        int ret = 0;
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if((row[i]+column[j]&1)==0) ret++;
            }
        }
        return ret;
    }

    Map<Integer, List<String>> map;
    public void buildDict(String[] dictionary) {
        for (String str:dictionary){
            List<String> list = map.getOrDefault(str.length(), new ArrayList<>());
            list.add(str);
            map.put(str.length(),list);
        }
    }

    public boolean search(String searchWord) {
        List<String> list = map.getOrDefault(searchWord.length(), null);
        if(list == null) return false;
        for (String str:list){
            int cnt = 0;
            for (int i=0;i<str.length();i++){
                if(searchWord.charAt(i) == str.charAt(i)) continue;
                cnt++;
                if(cnt>1) break;
            }
            if(cnt == 1) return true;
        }
        return false;
    }

    public int minCostToMoveChips(int[] position) {
        int one = 0 , two = 0;
        for (int i=0;i<position.length;i++){
            if((position[i]&1) == 0) one++;
            else two++;
        }
        return one<two?one:two;
    }

    private boolean compare(String s, String first) {
        if(s.length()<first.length()) return false;
        for (int i=0;i<first.length();i++){
            if(first.charAt(i)!= s.charAt(i)) return false;
        }
        return true;
    }


    char[] exp;
    public List<Integer> diffWaysToCompute(String expression) {
        exp = expression.toCharArray();
        return dfs(0,exp.length-1);
    }

    private List<Integer> dfs(int l, int r) {
        List<Integer> curRet = new ArrayList<>();
        for (int i=l;i<=r;i++){
            if(Character.isDigit(exp[i])) continue;
            List<Integer> lList = dfs(l,i-1),
                    rList = dfs(i+1,r);
            for (int num1:lList){
                for (int num2:rList){
                    int cur = 0;
                    if(exp[i] == '+') cur = num1+num2;
                    else if(exp[i] == '-') cur = num1-num2;
                    else cur = num1*num2;
                    curRet.add(cur);
                }
            }
        }
        if(curRet.isEmpty()){
            int cur = 0;
            for (int i=l;i<=r;i++){
                cur = cur*10+exp[i]-'0';
            }
            curRet.add(cur);
        }
        return curRet;
    }

    class MyCalendar {

        TreeSet<int[]> set;
        public MyCalendar() {
            set = new TreeSet<>((o1, o2) -> {
                if(o1[1]<=o2[0]) return 1;
                else if(o1[0]>=o2[1]) return -1;
                else return 0;
            });
        }

        public boolean book(int start, int end) {
            return set.add(new int[]{start,end});
        }
    }

    double ret = 0;
    Queue<Integer> queue = new LinkedList<>();
    int size = 0;
    public void MovingAverage(int size) {
        this.size = size;
    }

    public double next(int val) {
        if (queue.size()==size){
            ret -= queue.poll();
        }
        queue.offer(val);
        ret += val;
        return ret/queue.size();
    }

    public int arrayNesting(int[] nums) {
        boolean[] flag = new boolean[nums.length];
        int ret = 0;
        for (int i=0;i<nums.length;i++){
            if(flag[nums[i]]) continue;
            Set<Integer> set = new HashSet<>();
            dfs3(nums[i],nums,set,flag);
            ret = Math.max(ret,set.size());
        }
        return ret;
    }

    private void dfs3(int num, int[] nums, Set<Integer> set, boolean[] flag) {
        if(set.contains(num)) return;
        set.add(num);
        flag[num] = true;
        dfs3(nums[num],nums,set, flag);
    }

    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int row = grid.length,column = grid[0].length;
        List<List<Integer>> ret = new ArrayList<>();
        int[][] newGrid = new int[row][column];
        for (int i=0;i<row;i++){
            for(int j=0;j<column;j++){
                int val = column*i+j+k;
                int x = (val/column)%row;
                int y = val%column;
                newGrid[x][y] = grid[i][j];
            }
        }
        for (int i=0;i<row;i++){
            ret.add( Arrays.stream(newGrid[i]).boxed().collect(Collectors.toList()));
        }
        return ret;
    }

    public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
    }

    public TreeNode pruneTree(TreeNode root) {
        int cnt = dfs1(root);
        return cnt == 0?null:root;
    }

    private int dfs1(TreeNode root) {
        if(root == null) return 0;
        int left = dfs1(root.left);
        if(left == 0) {
            root.left = null;
        };
        int right = dfs1(root.right);
        if(right == 0){
            root.right = null;
        }
        return root.val+left+right;
    }

    public int minStartValue(int[] nums) {
        int startValue = 1,sum=0;
        for (int val:nums){
            sum += val;
            if(sum<0){
                startValue = Math.max(startValue,1-sum);
            }

        }
        return startValue;
    }

    @Test
    public void main() {
        //replaceWords(Arrays.asList(new String[]{"cat","bat","rat"}),"the cattle was rattled by the battery");
        //diffWaysToCompute("2-1-1");
        //asteroidCollision(new int[]{-2,-2,-3,5});
        //shiftGrid(new int[][]{{1},{2},{3},{4},{7},{6},{5}},23);
        //intersectionSizeTwo(new int[][]{{1, 2}, {2, 3}, {2, 4}, {4, 5}});
        fractionAddition("-5/2+10/3+7/9");
    }



    public String fractionAddition(String expression) {
        if(expression.charAt(0)!='-'){
            expression = "+"+expression;
        }
        char[] chars = expression.toCharArray();
        Queue<Integer> queue1 = new ArrayDeque<>();
        Queue<Integer> queue2 = new ArrayDeque<>();
        int val = 1;
        for (int i=0;i<chars.length;i++){
            if(chars[i]=='/') {
                int cur;
                if(i+2<chars.length&&chars[i+2]=='0'){
                    cur = 10;
                }else cur = chars[i+1]-'0';
                val*=cur;
                queue2.offer(cur);
            }
            if(chars[i] == '+' || chars[i] == '-'){
                int cur;
                if(chars[i+2]=='0'){
                    cur = 10;
                }else cur = chars[i+1]-'0';
                queue1.offer(chars[i] == '+' ?cur:cur*-1);
            }
        }
        int molecule = 0;
        while (!queue1.isEmpty()){
            molecule += queue1.poll()*(val/queue2.poll());
        }
        int res = gcd(molecule,val);
        molecule /= res;
        val /= res;
        if(val<0&&molecule>0) {
            val = -val;
            molecule = -molecule;
        }
        return molecule +"/"+ val;
    }

    int gcd(int a,int b){
        if(b == 0)
            return a;
        return gcd(b,a%b);
    }


    // 区间不是连续的
    // 1.先考虑如何排序
    // 2.在考虑排序后如何取值
    public int intersectionSizeTwo(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o2[1] - o1[1]);
        int l = intervals[0][0],r = intervals[0][1];
        int ret = 2;
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            if(r == cur[0]){ //1个交集
                r = cur[0]+1;
                ret++;
            }else if(r<cur[0]){//0个家评级
                r = cur[0]+1;
                ret+=2;
            }
        }
        return ret;
    }

    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int cur = start,l = 0,r=0,len = distance.length;
        while (cur!=destination){
            l += distance[cur];
            cur = (cur+1)%len;
        }
        while (cur!=start){
            l += distance[cur];
            cur = (cur+1)%len;
        }
        return Math.min(l,r);
    }
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        //检查每个相邻关系是否都出现过
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] sequence:sequences){
            for (int i=0;i<sequence.length-1;i++){
                Set<Integer> set = map.getOrDefault(sequence[i], new HashSet<>());
                set.add(sequence[i+1]);
                map.put(sequence[i],set);
            }
        }
        for (int i=0;i<nums.length-1;i++){
            if(!map.getOrDefault(nums[i],new HashSet<>()).contains(nums[i+1])) return false;
        }
        return true;
    }

    TreeNode root,cur;
    Queue<TreeNode> deque = new ArrayDeque<>();
    public void CBTInserter(TreeNode root) {
        this.root = root;
        while (root!=null){
            if(root.left!=null) deque.offer(root.left);
            else {
                cur = root;
                break;
            }
            if(root.right!=null) deque.offer(root.right);
            else {
                cur = root;
                break;
            }
        }
    }

    public int insert(int val) {
        if(cur.left == null){
            cur.left = new TreeNode(val);
            deque.offer(cur.left);
        }
        if(cur.right == null){
            cur.right = new TreeNode(val);
            deque.offer(cur.right);
            cur = deque.poll();
        }
        return 1;
    }

    public TreeNode get_root() {
        return root;
    }



}
